The present invention relates generally to error-correction coding and, more particularly, to trellis codes and to parallel concatenated convolutional coding, i.e., turbo coding.
A new class of forward error control codes, referred to as turbo codes, offers significant coding gain for power limited communication channels. Turbo codes are generated by using two or more recursive systematic encoders operating on different orderings of the same information bits. A subset of the code bits generated by each encoder is transmitted to maintain bandwidth efficiency. Turbo decoding involves an iterative algorithm in which probability estimates of the information bits that are derived for one of the code words are fed back to a probability estimator for the other code word. Each iteration of processing generally increases the reliability of the probability estimates. This process continues, alternately decoding the two code words until the probability estimates can be used to make reliable decisions.
The maximum a posteriori (MAP) algorithm introduced by Bahl, Cocke, Jelinek, and Raviv in "Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate", IEEE Transactions on Information Theory, March 1974, pp. 284-287, is particularly useful as a component decoder in decoding parallel concatenated convolutional codes, i.e., turbo codes. The MAP algorithm is used in the turbo decoder to generate a posteriori probability estimates of the systematic bits (i.e., information bits) in the code word. These probability estimates are used as a priori symbol probabilities for the second MAP decoder. Three fundamental terms in the MAP algorithm are: forward and backward state probability functions (the alpha and beta functions, respectively) and the a posteriori transition probabilities (the sigma function).
It is desirable to reduce the time for computation and memory required in turbo decoding, such as by providing a method for performing forward and reverse recursions simultaneously, thereby improving decoder performance even further.